//
//  Problem40.swift ✅
//  TestProject 40. 组合总和 II
//
//  Created by 武侠 on 2020/8/25.
//  Copyright © 2020 zhulong. All rights reserved.
//

import UIKit

/*
 40. 组合总和 II
 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

 candidates 中的每个数字在每个组合中只能使用一次。

 说明：
 所有数字（包括目标数）都是正整数。
 解集不能包含重复的组合。
 
 示例 1:
 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 所求解集为:
 [
   [1, 7],
   [1, 2, 5],
   [2, 6],
   [1, 1, 6]
 ]
 
 示例 2:
 输入: candidates = [2,5,2,1,2], target = 5,
 所求解集为:
 [
   [1,2,2],
   [5]
 ]
 */
@objcMembers class Problem40: NSObject {
    func solution() {
        print(combinationSum([10,1,2,7,6,1,5], 8))
        
        print(combinationSum([2,5,2,1,2], 5))
    }
    
    // 解题思路：回溯法，采用树结构
    //
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        if candidates.count == 0 {
            return []
        }
        
        var lists:[[Int]] = []
        var path:[Int] = []

        combinaNext(candidates.sorted(), 0, target, &path, &lists)
        return lists
    }
    
    func combinaNext(_ candidates:[Int], _ beigin: Int, _ target: Int, _ path: inout [Int], _ lists: inout[[Int]]) {
        
        if target < 0 {         // 不合适，放弃这颗枝
            return
        }
        if target == 0 {        // 找到目前，path符合
            if lists.contains(path) == false {
                lists.append(path)
            }
            return
        }
        
        
        for i in beigin..<candidates.count {
            if target - candidates[i] < 0 {     // 剪枝，因为不符合，放弃递归
                break
            }
            
            // 排序后的连续相同的2个数字，跳过，可参考3数之和
            if (i > beigin && candidates[i] == candidates[i - 1]) {
                continue;
            }

            path.append(candidates[i])
            combinaNext(candidates, i + 1, target - candidates[i], &path, &lists)
            
            // 删除上一颗枝
            path.removeLast()
        }
    }
}
